package sort;

import java.util.Arrays;

/**
 * @author Europa
 * @create 2020-05-15 1:14
 */
public abstract class Sort {

    /**
     * 排序
     *
     * @param array int数组
     */
    public abstract void sort(int[] array);

    /**
     * 比较操作
     *
     * @param perv 当前元素
     * @param next 下一个元素
     * @return 当前元素 < 下一个元素 返回true,反之false
     */
    boolean less(int perv, int next) {
        return perv < next;
    }

    /**
     * 当前元素与下一个元素交换位置
     *
     * @param array int数组
     * @param prev  当前元素的索引
     * @param next  下一个元素的索引
     */
    void exchange(int[] array, int prev, int next) {
        int temp = array[prev];
        array[prev] = array[next];
        array[next] = temp;
    }

    /**
     * 打印数组
     *
     * @param array int数组
     */
    public static void show(int[] array) {
        System.out.println("tearDown() array = " + Arrays.toString(array));
    }

    /**
     * 当前数组是否有序(升序)
     *
     * @param array int数组
     * @return 升序true, 反之false
     */
    public static boolean isSorted(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i - 1] > array[i]) {
                System.err.println("not sorted: index = " + (i - 1) + ", array[i - 1] = " + array[i - 1] + ", array[i] = " + array[i]);
                return false;
            }
        }
        return true;
    }

    /**
     * 二分查找
     *
     * @param array  有序数组(升序)
     * @param target 目标值
     * @return 存在返回true, 反之false
     */
    public static boolean search(int[] array, int target) {
        //左边界索引
        int left = 0;
        //右边界索引
        int right = array.length - 1;
        //左 <= 右 时停止循环
        while (left <= right) {
            //中间索引 = (左 + 右) / 2
            int mid = (left + right) / 2;
            //中间值 = array[中间索引]
            int mark = array[mid];
            if (mark == target) {
                return true;
            }
            if (mark > target) {
                //中间值大于目标时,右 = 中间索引 - 1
                right = mid - 1;
            } else {
                //中间值小于目标时,左 = 中间索引 + 1
                left = mid + 1;
            }
        }
        return false;
    }

    /*
     * @param src       源数组
     * @param srcPos    源数组中的起始位置
     * @param dest      目标数组
     * @param destPos   目标数据中的起始位置
     * @param length    要复制的数组元素的数目
     * void arrayCopy(Object src, int srcPos, Object dest, int destPos, int length);
     */
}
